home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / amiga / hdf / hdf.lha / DFIMCOMP.C < prev    next >
Encoding:
C/C++ Source or Header  |  1980-02-06  |  35.8 KB  |  1,260 lines
  1. /*****************************************************************************
  2. * 
  3. *              NCSA HDF version 3.10r3
  4. *                Dec 6, 1990
  5. *
  6. * NCSA HDF Version 3.10r3 source code and documentation are in the public
  7. * domain.  Specifically, we give to the public domain all rights for future
  8. * licensing of the source code, all resale rights, and all publishing rights.
  9. * 
  10. * We ask, but do not require, that the following message be included in all
  11. * derived works:
  12. * 
  13. * Portions developed at the National Center for Supercomputing Applications at
  14. * the University of Illinois at Urbana-Champaign.
  15. * 
  16. * THE UNIVERSITY OF ILLINOIS GIVES NO WARRANTY, EXPRESSED OR IMPLIED, FOR THE
  17. * SOFTWARE AND/OR DOCUMENTATION PROVIDED, INCLUDING, WITHOUT LIMITATION,
  18. * WARRANTY OF MERCHANTABILITY AND WARRANTY OF FITNESS FOR A PARTICULAR PURPOSE
  19. * 
  20. *****************************************************************************/
  21.  
  22. #ifdef RCSID
  23. static char RcsId[] = "@(#)$Revision: 3.4 $";
  24. #endif
  25. /*
  26. $Header: /pita/work/HDF/dev/RCS/src/dfimcomp.c,v 3.4 90/07/02 10:12:07 clow beta $
  27.  
  28. $Log:    dfimcomp.c,v $
  29.  * Revision 3.4  90/07/02  10:12:07  clow
  30.  * some cosmetic modifications
  31.  * 
  32. */
  33. /************************************************************************/
  34. /*  Module Name : imcomp                        */
  35. /*  Exports     : DFCimcomp(), DFCunimcomp()                */
  36. /*  Purpose     : Compresses color images               */
  37. /*  Author  : Eng-Kiat Koh                      */
  38. /*  Date    : June 30th, 1988                   */
  39. /*  Functions   : DFCimcomp(), compress(), init_global(), cnt_color()   */
  40. /*        set_palette(), fillin_color(), map(), nearest_color() */
  41. /*        DFCunimcomp(), sqr()                                  */
  42. /************************************************************************/
  43.  
  44. struct rgb
  45. {
  46.     unsigned char c[3];
  47. };
  48.  
  49. #include "df.h"
  50.  
  51. #define PALSIZE 256
  52. #define BIT8 0
  53. #define BIT24 1
  54.  
  55. #ifndef MAC
  56. #define MAXCOLOR 32768
  57. #else /*MAC*/
  58. #define MAXCOLOR 768
  59. #endif /*MAC*/
  60.  
  61. #ifndef NULL
  62. #   define NULL 0
  63. #endif
  64.  
  65. #define RED 0
  66. #define GREEN 1
  67. #define BLUE 2
  68. #define EPSILON 0.5
  69. #define LO 1
  70. #define HI 0
  71.  
  72. /* struct rgb
  73. {
  74.   unsigned char c[3];
  75. };
  76. */
  77. struct box
  78. {
  79.   float bnd[3][2];
  80.   int *pts;
  81.   int nmbr_pts;
  82.   int nmbr_distinct;
  83.   struct box *left;
  84.   struct box *right;
  85. };
  86.  
  87.  
  88. unsigned char *new_pal;          /* pointer to new palette           */
  89.  
  90.  
  91. static int *hist = (int *)NULL;    /* histogram for distinct colors    */
  92. static struct box *frontier = (struct box *)NULL; /* pointer to the */
  93.                           /* list of boxes */
  94. static struct rgb *distinct_pt = (struct rgb *)NULL; /* contains all */
  95.                              /* distinct rgb points */
  96.  
  97. static void sel_palette(int, int, struct rgb *); 
  98. static void compress();
  99. static void init_global();
  100. static int cnt_color();
  101. static void set_palette();
  102. static void fillin_color();
  103. static int indx();
  104. static void map();
  105. static int nearest_color();
  106. static long int sqr();
  107. static void init(int, int, struct rgb *);
  108. static int partition();
  109. static struct box *find_box();
  110. static void split_box();
  111. static void assign_color();
  112. static int select_dim();
  113. static float find_med();
  114. static void classify();
  115. static int next_pt();
  116.  
  117. /* extern char *calloc(); */
  118.  
  119. static struct rgb *color_pt = (struct rgb *)NULL; /*contains the hi-lo */
  120.                           /*colors for each block*/
  121. static unsigned char *image;    /* contains the compressed image            */
  122. static int trans[MAXCOLOR];     /* color translation table                  */
  123.  
  124. /************************************************************************/
  125. /*  Function    : DFCimcomp                                             */
  126. /*  Purpose : Performs Imcomp Compression                           */
  127. /*  Parameters  :                                                       */
  128. /*    xdim, ydim - dimensions of image                                  */
  129. /*                 IT IS ASSUMED THAT THE DIMENSIONS ARE A MULTIPLE OF 4*/
  130. /*    in, out    - input image array and output image buffer size of in */
  131. /*                 is xdim*ydim bytes for 8 bit per pixel mode. It is 3 */
  132. /*                 times that for 24 bits per pixel mode. The output    */
  133. /*                 buffer is always (xdim*ydim)/4.                      */
  134. /*    in_pal     - input palette. Consist of rgb triples unlike seq-type*/
  135. /*                 palette. This is a NULL pointer if operating at the  */
  136. /*                 24 bit per pixel mode.                               */
  137. /*    out_pal    - output palette. Consist of PALSIZE color entries.    */
  138. /*                 each entry is an rgb triple.                         */
  139. /*    mode       - Either BIT8 or BIT24                                 */
  140. /*  Returns     : none                          */
  141. /*  Called by   : External routines                                     */
  142. /*  Calls       : init_global(), compress(), cnt_color(), set_palette(),*/
  143. /*        sel_palette(), map()                                  */
  144. /************************************************************************/
  145.  
  146. void DFCimcomp(xdim, ydim, in, out, in_pal, out_pal, mode)
  147. int32 xdim, ydim;
  148. int mode;
  149. char in[], out[], in_pal[], out_pal[];
  150. {
  151.   unsigned char raster[48];
  152.   int blocks, nmbr, i, j, k, l, x, y;
  153.   void init_global();
  154.   void compress();
  155.   int cnt_color();
  156.   void set_palette();
  157.   void sel_palette(int, int, struct rgb *);
  158.   void map();
  159.   void fillin_color();
  160.  
  161.   init_global(xdim, ydim, out, out_pal);
  162.  
  163.   /* compress pixel blocks */
  164.   blocks = 0;
  165.   for (i=0; i<(ydim/4); i++)
  166.     for (j=0; j<(xdim/4); j++)
  167.     {
  168.       switch (mode)
  169.       {
  170.         case BIT8 : /* 8 bit per pixel format */
  171.             k = 0;
  172.             for (y=(i*4); y<(i*4+4); y++)
  173.               for (x=(j*4); x<(j*4+4); x++)         
  174.               {
  175.             l = y*xdim + x;
  176.             raster[k++] = (unsigned char) in_pal[3 * (unsigned char)in[l]];
  177.             raster[k++] = (unsigned char) in_pal[3 * (unsigned char)in[l] + 1];
  178.             raster[k++] = (unsigned char) in_pal[3 * (unsigned char)in[l] + 2];
  179.               } /* end of for x */
  180.             compress(raster,blocks);
  181.             break;
  182.  
  183.       case BIT24: /* 24 bit per pixel format */
  184.             k = 0;
  185.             for (y=(i*4); y<(i*4+4); y++)
  186.               for (x=(j*4); x<(j*4+4); x++)         
  187.               {
  188.             l = 3 *(y*xdim + x);
  189.             raster[k++] = (unsigned char) in[l];
  190.             raster[k++] = (unsigned char) in[l+1];
  191.             raster[k++] = (unsigned char) in[l+2];
  192.               } /* end of for x */
  193.             compress(raster,blocks);
  194.             break;
  195.     
  196.     default   : /* unsupported format */
  197.             printf("Error : Unsupported Format \n");
  198.             exit(1);
  199.             break;
  200.       } /* end of switch */
  201.       
  202.       blocks++;
  203.     } /* end of for j */
  204.  
  205.   /* set palette */
  206.   nmbr = cnt_color(blocks);
  207. /*
  208.   printf("Number of colors %d \n", nmbr);
  209. */
  210.   if (nmbr <= PALSIZE)
  211.     set_palette(blocks);
  212.   else
  213.   {
  214.     sel_palette(blocks,nmbr,color_pt);
  215.     map(blocks);
  216.   }
  217.  
  218.   fillin_color(blocks);
  219.  
  220. } /* end of DFCimcomp */
  221.  
  222.  
  223.  
  224.  
  225.  
  226.  
  227. /************************************************************************/
  228. /*  Function    : compress                                  */
  229. /*  Purpose : Given a block of 16 pixels, sets up a 16 bit bitmap   */
  230. /*                and assigns a lo and hi color for the block. For block*/
  231. /*                i, hi color is stored in color_pt[2i] and lo in       */
  232. /*                color_pt[2i+1]. Each color is then reduced to 15 bits */
  233. /*                by truncating the lower order 3 bits of each component*/
  234. /*  Parameter   :                           */
  235. /*    raster     - contains the 16 pixels of a block. Each pixel is 3   */
  236. /*         bytes, 1 byte for each color component               */
  237. /*    block  - pixel block number                                   */
  238. /*  Returns     : none                                                  */
  239. /*  Called by   : DFCimcomp()                       */
  240. /*  Calls       : none                          */
  241. /************************************************************************/
  242.  
  243. static void compress(raster, block)
  244. unsigned char raster[];
  245. int block;
  246. {
  247.   float y[16], y_av;
  248.   int i, j, k, l, bit;
  249.   int high, hi, lo;
  250.   int c_hi[3], c_lo[3];
  251.  
  252.   /* calculate luminance */
  253.   y_av = 0.0;
  254.   for (i=0; i<16; i++)
  255.   {
  256.     j = 3*i;
  257.     y[i] = 0.3*(float)raster[j] + 0.59*(float)raster[j+1] + 
  258.            0.11*(float)raster[j+2];
  259. /*    printf("compress: y[%d] is %f\n",i,y[i]);*/
  260.     y_av = y_av + y[i];
  261.   }
  262.   y_av = y_av / 16.0;
  263. /*  printf("y_av is %f\n",y_av); */
  264.  
  265.   /* initialize c_hi and c_lo */
  266.   for (i=RED; i<=BLUE; i++)
  267.   {
  268.     c_hi[i] = 0;
  269.     c_lo[i] = 0;
  270.   }
  271.  
  272.   /* build bit map */
  273.   k = 4 * block;
  274.   high = 0;
  275.   hi = 2 * block;
  276.   lo = hi + 1;
  277.   for (i=0; i<2; i++)
  278.   {
  279.     bit = 128;
  280.     for (j = (i*8); j<(i*8+8); j++)
  281.     {
  282.       if (y[j] > y_av)
  283.       {
  284.     image[k] = image[k] | bit;
  285.     high++;
  286.         for (l=RED; l<= BLUE; l++)
  287.       c_hi[l] = c_hi[l] + (int)raster[3*j+l];
  288.       }
  289.       else
  290.       {
  291.     for (l=RED; l<=BLUE; l++)
  292.           c_lo[l] = c_lo[l] + (int)raster[3*j+l];
  293.       } /* end of if */
  294.  
  295.       bit = bit >> 1;
  296.     } /* end of for j */
  297.    
  298.     k++;
  299.   } /* end of for i */
  300.  
  301.   /* calculate hi lo color */
  302.   for (i=RED; i<=BLUE; i++)
  303.   {
  304.     if (high != 0)
  305.       color_pt[hi].c[i] = (int)((float)c_hi[i] / (float)high);
  306.     if (high != 16)
  307.       color_pt[lo].c[i] = (int)((float)c_lo[i] / (float)(16 - high));
  308.     color_pt[hi].c[i] = color_pt[hi].c[i] >> 3;
  309.     color_pt[lo].c[i] = color_pt[lo].c[i] >> 3;
  310.  
  311.   }
  312. } /* end of compress */
  313.  
  314.  
  315.  
  316.  
  317.  
  318.  
  319. /************************************************************************/
  320. /*  Function    : init_global                       */
  321. /*  Purpose : Allocates memory for global variables                 */
  322. /*  Parameter   :                           */
  323. /*    xdim, ydim - x and y dimension of image               */
  324. /*    out        - pointer to output buffer                             */
  325. /*    out_pal    - pointer to output palette                            */
  326. /*  Returns     : none                              */
  327. /*  Called by   : DFCimcomp()                       */
  328. /*  Calls       : none                          */
  329. /************************************************************************/
  330.  
  331. static void init_global(xdim, ydim, out, out_pal)
  332. int32 xdim, ydim;
  333. char *out, *out_pal;
  334. {
  335.   int i, j;
  336.  
  337.   /* allocate memory */
  338.   image = (unsigned char *) out;
  339.   new_pal = (unsigned char *) out_pal;
  340.   if (color_pt) DFIfreespace((char *) color_pt);
  341.   color_pt = (struct rgb *)DFIgetspace((unsigned)((xdim*ydim)/8) *
  342.                        sizeof(struct rgb));
  343.  
  344.   if (image == NULL || color_pt == NULL || new_pal == NULL)
  345.   {
  346.     printf("Error : Out of Memory\n");
  347.     exit(1);
  348.   }
  349.  
  350.   /* initialize */
  351.   for (i=0; i<(xdim*ydim/4); i++)
  352.     image[i] = 0;
  353.  
  354.   for (i=0; i<(xdim*ydim/8); i++)
  355.     for (j=RED; j<= BLUE; j++)
  356.       color_pt[i].c[j] = 0;
  357.  
  358.   for (i=0; i<MAXCOLOR; i++)
  359.     trans[i] = -1;
  360. } /* end of init_global */
  361.  
  362.  
  363.  
  364.  
  365.  
  366. /************************************************************************/
  367. /*  Function    : cnt_color                                 */
  368. /*  Purpose : Counts the number of distinct colors compressd image  */
  369. /*  Parameter   :                           */
  370. /*    blocks     - total number of pixel blocks             */
  371. /*  Returns     : Number of distinct colors                             */
  372. /*  Called by   : DFCimcomp()                                           */
  373. /*  Calls       : indx()                        */
  374. /************************************************************************/
  375.  
  376. static int cnt_color(blocks)
  377. int blocks;
  378. {
  379.   int temp[MAXCOLOR];
  380.   int i, k, count;
  381.   int indx();
  382.  
  383.   for (i=0; i<MAXCOLOR; i++)
  384.     temp[i] = -1;
  385.  
  386.   for (i=0; i<(2*blocks); i++)
  387.   {
  388.     k = indx(color_pt[i].c[RED],color_pt[i].c[GREEN],color_pt[i].c[BLUE]);
  389. /*    printf("cnt_color: k is %d\n",k); */
  390.     temp[k] = 0;
  391.   }
  392.  
  393.   count  = 0;
  394.   for (i = 0; i< MAXCOLOR; i++)
  395.     if (temp[i] == 0)
  396.       count++;
  397.  
  398.   return count;
  399. } /* end of cnt_color */
  400.  
  401.  
  402.  
  403.  
  404.  
  405. /************************************************************************/
  406. /*  Function    : set_palette                       */
  407. /*  Purpose : The number of distinct colors is less than the desired*/
  408. /*                output palette size. Therefore each distinct color can*/
  409. /*        be a palette entry. Function enters each distinct     */
  410. /*                color as a palette entry and sets up the translation  */
  411. /*                table. It also shifts each color component left 3 bits*/
  412. /*                so that each color component is again 8 bits wide     */
  413. /*  Parameter   :                           */
  414. /*    blocks     - total number of pixel blocks                         */
  415. /*  Returns     : none                          */
  416. /*  Called by   : DFCimcomp()                       */
  417. /*  Calls       : indx()                        */
  418. /************************************************************************/
  419.  
  420. static void set_palette(blocks)
  421. int blocks;
  422. {
  423.   int ent, i, k;
  424.   int indx();
  425.  
  426.   ent = 0;
  427.   for (i = 0; i<(2*blocks); i++)
  428.   {
  429.     k = indx(color_pt[i].c[RED],color_pt[i].c[GREEN],color_pt[i].c[BLUE]);
  430.     if (trans[k] == -1)
  431.     {
  432.       new_pal[3*ent] = color_pt[i].c[RED] << 3;
  433.       new_pal[3*ent+1] = color_pt[i].c[GREEN] << 3;
  434.       new_pal[3*ent+2] = color_pt[i].c[BLUE] << 3;  
  435.       trans[k] = ent;
  436.       ent++;
  437.     }
  438.   }
  439. } /* end of set_palette */
  440.  
  441.  
  442.  
  443.  
  444.  
  445. /************************************************************************/
  446. /*  Function    : fillin_color                      */
  447. /*  Purpose : For each pixel block, fills in the pointers into the  */
  448. /*                palette.                                              */
  449. /*  Parameter   :                           */
  450. /*    blocks     - total number of pixel blocks             */
  451. /*  Returns     : none                          */
  452. /*  Called by   : DFCimcomp()                       */
  453. /*  Calls       : none                          */
  454. /************************************************************************/
  455.  
  456. static void fillin_color(blocks)
  457. int blocks;
  458. {
  459.   int i, j, k;
  460.  
  461.   for (i=0; i<blocks; i++)
  462.     for (j=HI; j<=LO; j++)
  463.     {
  464.       k = indx(color_pt[2*i+j].c[RED],color_pt[2*i+j].c[GREEN],
  465.            color_pt[2*i+j].c[BLUE]);
  466.       image[i*4+2+j] = trans[k];
  467.     }
  468. } /* end of fillin_color */
  469.  
  470.  
  471.  
  472.  
  473.  
  474. /************************************************************************/
  475. /*  Function    : indx                          */
  476. /*  Purpose : Maps an rgb triple (5 bits each) to an integer array  */
  477. /*        index                         */
  478. /*  Parameter   :                           */
  479. /*    r, g, b    - color components                 */
  480. /*  Returns     : returns an array index                */
  481. /*  Called by   : set_palette(), fillin_color(), map()                  */
  482. /*  Calls       : none                          */
  483. /************************************************************************/
  484.  
  485. static int indx(r, g, b)
  486. unsigned char r, g, b;
  487. {
  488.   int temp;
  489.  
  490.   temp = 0;
  491.   temp = ((r & 0x1f) << 10) | ((g & 0x1f)  << 5) | (b & 0x1f);
  492.   return temp;
  493. } /* end of indx */
  494.  
  495.  
  496.  
  497.  
  498.  
  499.  
  500. /************************************************************************/
  501. /*  Function    : map                           */
  502. /*  Purpose : Maps a color_pt to the closest representative color   */
  503. /*        Sets up translation table             */
  504. /*  Parameter   :                           */
  505. /*    blocks     - total number of pixel blocks             */
  506. /*  Returns     : none                          */
  507. /*  Called by   : DFCimcomp()                       */
  508. /*  Calls       : nearest_color()                   */
  509. /************************************************************************/
  510.  
  511. static void map(blocks)
  512. int blocks;
  513. {
  514.   int i, k;
  515.   unsigned char r, g, b;
  516.   int indx();
  517.   int nearest_color();
  518.  
  519.   for (i=0; i<(2*blocks); i++)
  520.   {
  521.     k = indx(color_pt[i].c[RED], color_pt[i].c[GREEN], color_pt[i].c[BLUE]);
  522.  
  523.     if (trans[k] == -1)
  524.     {
  525.       r = (unsigned char) color_pt[i].c[RED]<<3;
  526.       g = (unsigned char) color_pt[i].c[GREEN]<<3;
  527.       b = (unsigned char) color_pt[i].c[BLUE]<<3;
  528.       trans[k] = nearest_color(r, g, b);
  529. /*
  530.       printf("map: %d %d %d mapped to %d %d %d\n", r, g, b, new_pal[trans[k]*3],
  531.           new_pal[trans[k]*3+1], new_pal[trans[k]*3+2]);
  532. */
  533.     }
  534.   }
  535. } /* end of map */
  536.   
  537.  
  538.  
  539.  
  540. /************************************************************************/
  541. /*  Function    : nearest_color                     */
  542. /*  Purpose : Finds the nearest palette color           */
  543. /*  Parameter   :                           */
  544. /*    r, g, b    - color component                  */
  545. /*  Returns     : Entry number of the closest color in the palette      */
  546. /*  Called by   : map()                         */
  547. /*  Calls       : sqr()                         */
  548. /************************************************************************/
  549.  
  550. static int nearest_color(r, g, b)
  551. unsigned char r, g, b;
  552. {
  553.   int i, near; 
  554.   long int min, error;
  555.   long int sqr();
  556.  
  557.   min = sqr(r-new_pal[0]) + sqr(g-new_pal[1]) + sqr(b-new_pal[2]);
  558.   near = 0;
  559.   for (i=1; i<PALSIZE; i++)
  560.   {
  561.     error = sqr(r-new_pal[3*i]) + sqr(g-new_pal[3*i+1]) + 
  562.         sqr(b-new_pal[3*i+2]);
  563.     if (error < min)
  564.     {
  565.     min = error;
  566.         near = i;
  567.     }
  568.   }
  569.  
  570.   return near;
  571. } /* end of nearest_color */
  572.  
  573.  
  574.  
  575.  
  576. /************************************************************************/
  577. /*  Function    : sqr                           */
  578. /*  Purpose : Computes the square of an integer         */
  579. /*  Parameter   :                           */
  580. /*    x      - an integer                       */
  581. /*  Returns     : The square of x                   */
  582. /*  Called by   : nearest_color()                   */
  583. /*  Calls       : none                          */
  584. /************************************************************************/
  585.  
  586. static long int sqr(x)
  587. unsigned char x;
  588. {
  589.   return (x*x);
  590. }
  591.  
  592.  
  593.  
  594.  
  595.  
  596. /************************************************************************/
  597. /*  Function    : DFCunimcomp                       */
  598. /*  Purpose : 'Decompresses' the compressed image           */
  599. /*  Parameter   :                           */
  600. /*    xdim, ydim - dimensions of image                  */
  601. /*    in, out    - Input buffer and output buffer. Size of input buffer */
  602. /*         is (xdim*ydim)/4. Size of output buffer is 4 times   */
  603. /*         that. It 'restores' images into seq-type files       */
  604. /*  Returns     : none                          */
  605. /*  Called by   : External routines                 */
  606. /*  Calls       : none                          */
  607. /************************************************************************/
  608.  
  609. void DFCunimcomp(xdim, ydim, in, out)
  610. int32 xdim, ydim;
  611. char in[], out[];
  612. {
  613.   int bitmap, temp;
  614.   int i, j, k, x, y;
  615.   unsigned char hi_color, lo_color;
  616.  
  617.   for (y=0; y<(ydim/4); y++)
  618.     for (x=0; x<xdim; x=x+4)
  619.     {
  620.       k = y*xdim + x;
  621.       hi_color = (unsigned char) in[k+2]; 
  622.       lo_color = (unsigned char) in[k+3];
  623.  
  624.       bitmap = ((unsigned char)in[k] << 8) | (unsigned char)in[k+1];
  625.  
  626.       for (i=(y*4); i<(y*4+4); i++)
  627.       {
  628.         temp = bitmap >> (3 + y*4 - i)*4;
  629.         for (j=x; j<(x+4); j++)
  630.         {
  631.       if ((temp & 8) == 8)
  632.         out[i*xdim+j] = (char) hi_color;
  633.       else
  634.         out[i*xdim+j] = (char) lo_color;
  635.       temp = temp << 1;
  636.     }
  637.       }
  638.     } /* end of for x */
  639. } /* end of DFCunimcomp */
  640.  
  641.  
  642.  
  643. /************************************************************************/
  644. /*  Module Name : color                         */
  645. /*  Exports     : sel_palette(); new_pal, pointer to a new color palette*/
  646. /*  Purpose     : Quantizes colors                  */
  647. /*  Author  : Eng-Kiat Koh                      */
  648. /*  Date    : June 30th, 1988                   */
  649. /*  Functions   : sel_palette(), init(), sort(), partition(), find_box()*/
  650. /*        split_box(), assign_color(), select_dim(), find_med() */
  651. /*                classify(), next_pt()                                 */
  652. /************************************************************************/
  653.  
  654.  
  655.  
  656.  
  657.  
  658.  
  659.  
  660. /************************************************************************/
  661. /*  Function    : sel_palette                       */
  662. /*  Purpose : Selects PALSIZE palette colors out of a list of colors*/
  663. /*        in color_pt                       */
  664. /*  Parameter   :                           */
  665. /*    blocks     - number of pixel blocks               */
  666. /*    distinct   - number of distinct colors                */
  667. /*    color_pt   - contains the lo hi colors for each pixel block       */
  668. /*  Returns     : none                          */
  669. /*  Called by   : DFCimcomp()                       */
  670. /*  Calls       : init(), split_box(), find_box(), assign_color()   */
  671. /************************************************************************/
  672.  
  673. static void sel_palette(blocks,distinct, color_pt)
  674. int blocks, distinct;
  675. struct rgb *color_pt;
  676. {
  677.   int boxes;
  678. /*  int i, j;*/
  679.   struct box *ptr;
  680.   struct box *find_box();
  681.   void init(int, int, struct rgb *);
  682.   void split_box();
  683.   void assign_color();
  684.  
  685.   init(blocks, distinct, color_pt);
  686.  
  687.   /* split box into smaller boxes with about equal number of points */
  688.   for (boxes=1; boxes < PALSIZE; boxes++)
  689.   {
  690. /*
  691.     ptr=frontier->right;
  692.     j = 0;
  693.     while (ptr != NULL)
  694.     {
  695.       printf("Box %d, distinct %d, total %d\n",j,ptr->nmbr_distinct,
  696.              ptr->nmbr_pts);
  697.       for (i=0; i<ptr->nmbr_distinct; i++)
  698.         printf("pt %d: %d %d %d",i,distinct_pt[ptr->pts[i]].c[RED],
  699.                 distinct_pt[ptr->pts[i]].c[GREEN], 
  700.             distinct_pt[ptr->pts[i]].c[BLUE]);
  701.       j++;
  702.       ptr = ptr->right;
  703.     }
  704. */
  705.  
  706.     ptr = find_box();
  707.     split_box(ptr);
  708.   } 
  709.  
  710.   assign_color();
  711. }
  712.  
  713.  
  714.  
  715.  
  716.  
  717.  
  718. /************************************************************************/
  719. /*  Function    : init                          */
  720. /*  Purpose : Initializes the global variables, sets up the first   */
  721. /*        box. It will contain all the color points     */
  722. /*  Parameter   :                           */
  723. /*    blocks     - number of pixel blocks               */
  724. /*    distinct   - number of distinct colors                */
  725. /*    color_pt   - contains the lo hi colors for each pixel block       */
  726. /*  Returns     : none                          */
  727. /*  Called by   : sel_palette()                     */
  728. /*  Calls       : none                          */
  729. /************************************************************************/
  730.  
  731. static void init(blocks, distinct, color_pt)
  732. int blocks, distinct;
  733. struct rgb *color_pt;
  734. {
  735.   int i, j, k, l;
  736.   int temp[MAXCOLOR];
  737.   struct box *first;
  738.   struct box *dummy;
  739.  
  740.   /* alloc memory */
  741.   if (hist) DFIfreespace((char *) hist);
  742.   if (distinct_pt) DFIfreespace((char*) distinct_pt);
  743.   hist = (int *)DFIgetspace((unsigned)distinct * sizeof(int));
  744.   distinct_pt = (struct rgb *)DFIgetspace((unsigned)distinct *
  745.                       sizeof(struct rgb));
  746.  
  747.   for (i=0; i<distinct; i++)
  748.     hist[i] = 0;
  749.  
  750.  
  751.   /* select distinct pts and set up histogram */
  752.   for (i=0; i<MAXCOLOR; i++)
  753.     temp[i] = -1;
  754.  
  755.   k = 0;
  756.   for (i=0; i<(2*blocks); i++)
  757.   {
  758.     j = (color_pt[i].c[RED] << 10) | (color_pt[i].c[GREEN] << 5) |
  759.         color_pt[i].c[BLUE];
  760.  
  761.     if (temp[j] == -1)
  762.     {
  763.       /* new pt */
  764.       temp[j] = k;
  765.       for (l=RED; l<=BLUE; l++)
  766.     distinct_pt[k].c[l] = color_pt[i].c[l];
  767.       k++;
  768.    }
  769.  
  770.    hist[temp[j]]++;
  771.   }
  772.  
  773.       
  774.   /* set up first box */
  775.   first = (struct box *)DFIgetspace(sizeof(struct box));
  776.   for (i=RED; i<=BLUE; i++)
  777.   {
  778.     first->bnd[i][LO] = 999.9;
  779.     first->bnd[i][HI] = -999.9;
  780.  
  781.     for (j=0; j<distinct; j++)
  782.     {
  783.       if (first->bnd[i][LO] > (float)distinct_pt[j].c[i])
  784.     first->bnd[i][LO] = (float)distinct_pt[j].c[i];
  785.  
  786.       if (first->bnd[i][HI] < (float)distinct_pt[j].c[i])
  787.     first->bnd[i][HI] = (float)distinct_pt[j].c[i];
  788.     } /* end of for j */
  789.  
  790.     first->bnd[i][LO] = first->bnd[i][LO] - EPSILON;
  791.     first->bnd[i][HI] = first->bnd[i][HI] + EPSILON;
  792.   } /* end of for i */
  793.  
  794.   first->pts = (int *)DFIgetspace((unsigned)distinct * sizeof(int));
  795.   for (i=0; i<distinct; i++)
  796.     first->pts[i] = i;
  797.   first->nmbr_pts = 2*blocks;
  798.   first->nmbr_distinct = distinct;
  799.  
  800.   dummy = (struct box *)DFIgetspace(sizeof(struct box));
  801.   frontier = dummy;
  802.   dummy->right = first;
  803.   first->left = dummy;
  804.   first->right = NULL;
  805.   dummy->nmbr_pts = 0;
  806.  
  807.   DFIfreespace((char *)first);
  808.   DFIfreespace((char *)dummy);
  809. } /* end of init */
  810.  
  811.  
  812.  
  813.  
  814.  
  815.  
  816.  
  817. /************************************************************************/
  818. /*  Function    : sort                          */
  819. /*  Purpose : Performs quick sort on the points in a box along a    */
  820. /*        given dimension                   */
  821. /*  Parameter   :                           */
  822. /*    l, r   - index of leftmost and rightmost element      */
  823. /*    dim    - dimension along which sorting is done        */
  824. /*    rank   - an array which carries the index of the points to be */
  825. /*         sorted                       */
  826. /*  Returns     : none                          */
  827. /*  Called by   : find_med()                        */
  828. /*  Calls       : partition()                       */
  829. /************************************************************************/
  830.  
  831. static void sort(l,r,dim, rank)
  832. int l, r, dim, rank[];
  833. {
  834.   int i;
  835.   int partition();
  836.   void sort();
  837.  
  838.   if (r > l)
  839.   {
  840.     i = partition(l, r, dim, rank);
  841.     sort(l, i-1, dim, rank);
  842.     sort(i+1, r, dim, rank);
  843.   }
  844. }
  845.  
  846.  
  847.  
  848.  
  849.  
  850.  
  851. /************************************************************************/
  852. /*  Function    : partition                     */
  853. /*  Purpose : Partitions the list into 2 parts as in the quick sort */
  854. /*        algorithm                     */
  855. /*  Parameter   :                           */
  856. /*    l, r   - index of leftmost and rightmost element      */
  857. /*    dim    - dimension along which sorting is done        */
  858. /*    rank   - an array which carries the index of the points to be */
  859. /*  Returns     : index where list is partitioned           */
  860. /*  Called by   : sort()                        */
  861. /*  Calls       : none                          */
  862. /************************************************************************/
  863.  
  864. static int partition(l, r, dim, rank)
  865. int l, r, dim, rank[];
  866. {
  867.   int i, j, temp;
  868.   char v;
  869.   
  870.   v = distinct_pt[rank[r]].c[dim];
  871.   i = l-1;
  872.   j = r;
  873.  
  874.   /* repeat until i and j crosses */
  875.   do
  876.   {
  877.     /* repeat until an element >= v is found */
  878.     do
  879.       i++;
  880.     while (distinct_pt[rank[i]].c[dim] < v);
  881.  
  882.     /* repeat until an element <= v is found */
  883.     do
  884.       j--;
  885.     while ((j>0) && (distinct_pt[rank[j]].c[dim] > v));
  886.  
  887.     /* swap pointers */
  888.     temp = rank[i];
  889.     rank[i] = rank[j];
  890.     rank[j] = temp;
  891.   }
  892.   while (i < j);
  893.  
  894.   /* position partitioning element at location i */
  895.   temp = rank[j];
  896.   rank[j] = rank[i];
  897.   rank[i] = rank[r];
  898.   rank[r] = temp;
  899.  
  900.   return i;
  901. }
  902.  
  903.  
  904.  
  905.  
  906.  
  907. /************************************************************************/
  908. /*  Function    : find_box                      */
  909. /*  Purpose : Finds the box with the largest number of color points */
  910. /*        The points need not necessarily be distinct. But in   */
  911. /*        order to partition the box, there must be at least  2 */
  912. /*        distinct points                   */
  913. /*  Parameter   : none                          */
  914. /*  Returns     : pointer to box selected for splitting         */
  915. /*  Called by   : sel_palette()                     */
  916. /*  Calls       : none                          */
  917. /************************************************************************/
  918.  
  919. static struct box *find_box()
  920. {
  921.   struct box *temp;
  922.   struct box *max;
  923.   int max_pts;
  924.  
  925.   max_pts = 1;
  926.   max = NULL;
  927.   temp = frontier->right;
  928.   while (temp != NULL)
  929.     if ((temp->nmbr_distinct > 1) && (max_pts < temp->nmbr_pts))
  930.     {
  931.       max_pts = temp->nmbr_pts;
  932.       max = temp;
  933.       temp = temp->right;
  934.     }
  935.     else
  936.       temp = temp->right;
  937.  
  938.   if (max == NULL)
  939.   {
  940.     printf("Error : Number of color points < palette \n");
  941.     exit(1);
  942.   }
  943.  
  944.   return max;
  945. }
  946.  
  947.  
  948.  
  949.  
  950.  
  951. /************************************************************************/
  952. /*  Function    : split_box                     */
  953. /*  Purpose : Splits a selected box into 2 and reinserts the 2 sub- */
  954. /*        boxes into the frontier list              */
  955. /*  Parameter   :                           */
  956. /*    ptr    - pointer to box to be split               */
  957. /*  Returns     : none                          */
  958. /*  Called by   : sel_palette()                     */
  959. /*  Calls       : find_med(), select_dim(), classify()          */
  960. /************************************************************************/
  961.  
  962. static void split_box(ptr)
  963. struct box *ptr;
  964. {
  965.   int dim, j, i;
  966.   float median;
  967.   struct box *l_child, *r_child;
  968.   int select_dim();
  969.   float find_med();
  970.   void classify();
  971.   
  972.   dim = select_dim(ptr);
  973.   median = find_med(ptr, dim);
  974.  
  975.   /* create 2 child */
  976.   l_child = (struct box *)DFIgetspace(sizeof(struct box));
  977.   r_child = (struct box *)DFIgetspace(sizeof(struct box));
  978.   
  979.   for (i=RED; i<=BLUE; i++)
  980.     for (j=HI; j<=LO; j++)
  981.     {
  982.       l_child->bnd[i][j] = ptr->bnd[i][j];
  983.       r_child->bnd[i][j] = ptr->bnd[i][j];
  984.     }
  985.   l_child->bnd[dim][HI] = median;
  986.   r_child->bnd[dim][LO] = median;
  987.  
  988.   classify(ptr,l_child);
  989.   classify(ptr,r_child);
  990.  
  991.   r_child->right = ptr->right;
  992.   r_child->left = l_child;
  993.   l_child->right = r_child;
  994.   l_child->left = ptr->left;
  995.   (ptr->left)->right = l_child;
  996.   if (ptr->right != NULL)
  997.     (ptr->right)->left = r_child;
  998. } /* end of split_box */
  999.  
  1000.  
  1001.  
  1002.  
  1003.  
  1004.  
  1005. /************************************************************************/
  1006. /*  Function    : assign_color                      */
  1007. /*  Purpose : Assigns a color to each box. It computes the average  */
  1008. /*        color of all the points in the box            */
  1009. /*        Sets up the new_pal buffer. Each color component is   */
  1010. /*        shifted left 3 bits because of the truncation when    */
  1011. /*        color_pt was set up                   */
  1012. /*  Parameter   : none                          */
  1013. /*  Returns     : none                          */
  1014. /*  Called by   : sel_palette()                     */
  1015. /*  Calls       : none                          */
  1016. /************************************************************************/
  1017.  
  1018.  
  1019. static void assign_color()
  1020. {
  1021.   struct box *temp;
  1022.   int ent, k, j;
  1023.   int c[3];
  1024.  
  1025.   temp = frontier->right;
  1026.   for (ent=0; ent<PALSIZE; ent++)
  1027.   {
  1028.     for (k=RED; k<=BLUE; k++)
  1029.       c[k] = 0;
  1030.  
  1031. /*
  1032.     printf("Box %d: number of pts %d\n", ent, temp->nmbr_pts);
  1033. */
  1034.  
  1035.     for (j=0; j<temp->nmbr_distinct; j++)
  1036.     {
  1037. /*
  1038.       printf("pt %d:", j);
  1039. */
  1040.       for (k=RED; k<=BLUE; k++)
  1041.       {
  1042. /*
  1043.         printf("%d ",distinct_pt[temp->pts[j]].c[k]);
  1044. */
  1045.     c[k] = c[k] + distinct_pt[temp->pts[j]].c[k]*hist[temp->pts[j]];
  1046.       }
  1047. /*
  1048.       printf("\n");
  1049. */
  1050.     }
  1051.  
  1052.     for (k=RED; k<=BLUE; k++)
  1053.     {
  1054.       c[k] = c[k] / temp->nmbr_pts;
  1055.       new_pal[3*ent+k] = c[k] << 3;
  1056.     }
  1057.     
  1058.     temp = temp->right;
  1059.   } /* end of for entry */
  1060. }
  1061.  
  1062.  
  1063.  
  1064.  
  1065.  
  1066. /************************************************************************/
  1067. /*  Function    : select_dim                        */
  1068. /*  Purpose : Selects the dimension with the largest spread         */
  1069. /*  Parameter   :                           */
  1070. /*    ptr    - pointer to desired box               */
  1071. /*  Returns     : dimension where the box is to be split        */
  1072. /*  Called by   : split_box()                       */
  1073. /*  Calls       : none                          */
  1074. /************************************************************************/
  1075.  
  1076. static int select_dim(ptr)
  1077. struct box *ptr;
  1078. {
  1079.   int i, j, low[3], high[3];
  1080.   int max;
  1081.  
  1082.  
  1083.   for (j=RED; j<=BLUE; j++)
  1084.   {
  1085.     low[j] = distinct_pt[ptr->pts[0]].c[j];
  1086.     high[j] = distinct_pt[ptr->pts[0]].c[j];
  1087.   }
  1088.  
  1089.   for (i=1; i<ptr->nmbr_distinct; i++)
  1090.     for (j=RED; j<=BLUE; j++)
  1091.     {
  1092.       if (low[j] > distinct_pt[ptr->pts[i]].c[j])
  1093.     low[j] = distinct_pt[ptr->pts[i]].c[j];
  1094.       if (high[j] < distinct_pt[ptr->pts[i]].c[j])
  1095.     high[j] = distinct_pt[ptr->pts[i]].c[j];
  1096.     }
  1097.  
  1098.   max = high[RED] - low[RED];
  1099.   i = RED;
  1100.   for (j=GREEN; j<=BLUE; j++)
  1101.     if (max < (high[j] - low[j]))
  1102.     {
  1103.       max = high[j] - low[j];
  1104.       i = j;
  1105.     }
  1106.  
  1107.   return i;
  1108. } /* end of select_dim */
  1109.  
  1110.  
  1111.  
  1112.  
  1113.  
  1114. /************************************************************************/
  1115. /*  Function    : find_med                      */
  1116. /*  Purpose : Finds the point where the box is to be split. It finds*/
  1117. /*        a point such that the 2 new boxes have about the same */
  1118. /*        number of color points.               */
  1119. /*  Parameter   :                           */
  1120. /*    ptr    - pointer to box to be split               */
  1121. /*    dim    - dimension to split box               */
  1122. /*  Returns     : point where the box is to be cut          */
  1123. /*  Called by   : split_box()                       */
  1124. /*  Calls       : next_pt()                     */
  1125. /************************************************************************/
  1126.  
  1127. static float find_med(ptr,dim)
  1128. struct box *ptr;
  1129. int dim;
  1130. {
  1131.   int i, j, count, next, prev;
  1132.   int *rank;
  1133.   float median;
  1134.   int next_pt();
  1135.   void sort();
  1136.  
  1137.   rank = (int *)DFIgetspace((unsigned)ptr->nmbr_distinct * sizeof(int));
  1138.   for (i=0; i<ptr->nmbr_distinct; i++)
  1139.     rank[i] = ptr->pts[i];
  1140.  
  1141.   sort(0,ptr->nmbr_distinct-1,dim,rank);
  1142. /*
  1143.   for (i=0; i<ptr->nmbr_distinct; i++)
  1144.     printf("find_med: sorted list is %d\n",distinct_pt[rank[i]].c[dim]);
  1145. */
  1146.   
  1147.  
  1148.   count = 0;
  1149.   i = 0;
  1150.   while ((i < ptr->nmbr_distinct) && (count < ptr->nmbr_pts/2))
  1151.   {
  1152.     next = next_pt(dim, i, rank, ptr->nmbr_distinct);
  1153.     for (j=i; j<next; j++)
  1154.       count = count + hist[rank[j]];
  1155.  
  1156.     prev = i;
  1157.     i = next; 
  1158.   }
  1159.  
  1160.   if (prev == 0)
  1161.   {
  1162.     /* the first distinct point overshot the median */
  1163.     median = (float)distinct_pt[rank[prev]].c[dim] + EPSILON;
  1164.   }
  1165.   else
  1166.     median = (float)distinct_pt[rank[prev-1]].c[dim] + EPSILON;
  1167.    
  1168.   DFIfreespace((char *) rank);
  1169.   return median;
  1170. } /* end of find_med */
  1171.   
  1172.  
  1173.  
  1174.  
  1175.  
  1176.  
  1177. /************************************************************************/
  1178. /*  Function    : classify                      */
  1179. /*  Purpose : Looks at the color points in the parent and selects   */
  1180. /*        the points that belong to the child           */
  1181. /*  Parameter   :                           */
  1182. /*    ptr    - pointer to parent                    */
  1183. /*    child  - pointer to child box                 */
  1184. /*  Returns     : none                          */
  1185. /*  Called by   : split_box()                       */
  1186. /*  Calls       : none                          */
  1187. /************************************************************************/
  1188.  
  1189. static void classify(ptr, child)
  1190. struct box *ptr, *child;
  1191. {
  1192.   int i, j;
  1193.   int *temp;
  1194.   int distinct, total;
  1195.  
  1196.   temp = (int *)DFIgetspace((unsigned)ptr->nmbr_distinct * sizeof(int));
  1197.  
  1198.   distinct = 0;
  1199.   total = 0;
  1200.   for (i=0; i<ptr->nmbr_distinct; i++)
  1201.   {
  1202.     j = ptr->pts[i];
  1203.     if ((((float)distinct_pt[j].c[RED] >= child->bnd[RED][LO]) &&
  1204.          ((float)distinct_pt[j].c[RED] <= child->bnd[RED][HI])) &&
  1205.         (((float)distinct_pt[j].c[GREEN] >= child->bnd[GREEN][LO]) &&
  1206.          ((float)distinct_pt[j].c[GREEN] <= child->bnd[GREEN][HI])) &&
  1207.         (((float)distinct_pt[j].c[BLUE] >= child->bnd[BLUE][LO]) &&
  1208.          ((float)distinct_pt[j].c[BLUE] <= child->bnd[BLUE][HI])))
  1209.     {
  1210.       /* pt is in new box */
  1211.       temp[distinct] = j;
  1212.       distinct++;
  1213.       total = total + hist[j];
  1214.     } /* end of if */
  1215.   } /* end of for i */
  1216.  
  1217.   /* assign points */
  1218.   child->nmbr_pts = total;
  1219.   child->nmbr_distinct = distinct;
  1220.   child->pts = (int *)DFIgetspace((unsigned)distinct * sizeof(int));
  1221.   for (i=0; i<distinct; i++)
  1222.     child->pts[i] = temp[i];
  1223.  
  1224.   DFIfreespace((char *)temp);
  1225.  
  1226. } /* end of classify */
  1227.  
  1228.  
  1229.  
  1230.  
  1231.  
  1232. /************************************************************************/
  1233. /*  Function    : next_pt                       */
  1234. /*  Purpose : Determines the next point that has a different value  */
  1235. /*        from the current point along  a dimension     */
  1236. /*  Parameter   :                           */
  1237. /*    dim    - dimension where box is to be split           */
  1238. /*    i      - index to current point               */
  1239. /*    rank       - sorted list of points to be searched starting from i */
  1240. /*    distinct   - length of sorted list                                */
  1241. /*  Returns     : index of point that has a different value     */
  1242. /*  Called by   : find_med                      */
  1243. /*  Calls       : none                          */
  1244. /************************************************************************/
  1245.  
  1246. static int next_pt(dim, i, rank, distinct)
  1247. int dim, i, rank[], distinct;
  1248. {
  1249.   int j;
  1250.   char old;
  1251.  
  1252.   old = distinct_pt[rank[i]].c[dim];
  1253.   for (j=(i+1); j<distinct; j++)
  1254.     if (distinct_pt[rank[j]].c[dim] != old)
  1255.       break;
  1256.  
  1257.   return j;
  1258. } /* end of next_pt */
  1259.  
  1260.